package com.xyzboom.compiler.fa.regex

import com.xyzboom.compiler.excepitons.fa.IllegalRegexException
import com.xyzboom.compiler.fa.EdgeType
import com.xyzboom.compiler.fa.FAEdge
import com.xyzboom.compiler.fa.NFA
import com.xyzboom.compiler.fa.NFANode

private val regOpPriority: HashMap<Char, Int> = hashMapOf(
    Pair('(', -1),
    Pair('|', 0),
    Pair('&', 100),
)
private const val allRegOp: String = "+*()|\\[]?."
private const val unaryRegOp: String = "+*?"
const val linker: Char = '&'


private class RegexParser(regex: String) {
    val symbolStack = ArrayList<Char>()
    val nfaStack = ArrayList<NFA<Int, Char>>()
    var state = 0
    val allNodes = HashSet<NFANode<Int, Char>>()
    private val newNode: NFANode<Int, Char>
        get() {
            val result = NFANode<Int, Char>(state++)
            allNodes.add(result)
            return result
        }
    val startNode: NFANode<Int, Char> = newNode
    val startNFA: NFA<Int, Char>
    val endNode: NFANode<Int, Char> = newNode
    fun handleMiddleContext(index: Int, regex: String): Int {
        var i = index + 1
        var escape = false
        var isFirst = true
        val edgeType = if (regex[i] == '^') {
            i++
            EdgeType.REVERSE
        } else EdgeType.NORMAL
//                var normalCount = 0
        while (true) {
            var c = regex[i]
            if (i >= regex.length) throw IllegalRegexException.lackOfChar(']')
            when {
                c == '\\' && !escape -> {
                    escape = true
                    i++
                    continue
                }

                c == ']' && !escape -> {
                    i++
                    break
                }

                else -> {
                    if (escape) {
                        val (escChar, handled, indexInc) = parseEscape(c, edgeType)
                        i += indexInc - 1
                        if (handled) {
                            i++
                            escape = false
                            continue
                        }
                        c = escChar
                    }
                    if (i == regex.length - 1) {
                        pushNewNFAWithCharOf(c, edgeType)
                        if (!isFirst) calc('|')
                        else isFirst = false
                    } else {
                        val nextI = i + 1
                        val nextC = regex[nextI]
                        if (nextC == '-') {
                            if (nextI >= regex.length - 1) throw IllegalRegexException.lackOfChar(']')
                            if (regex[nextI + 1] == ']') {
                                pushNewNFAWithCharOf(c, edgeType)
                                if (!isFirst) calc('|')
                                pushNewNFAWithCharOf(nextC)
                                calc('|')
                                return i + 3
                            } else {
                                val charTo = regex[nextI + 1]
                                if (charTo == c) {
                                    pushNewNFAWithCharOf(c, edgeType)
                                    if (!isFirst) calc('|')
                                    else isFirst = false
                                } else {
                                    var charNow = c
                                    while (true) {
                                        pushNewNFAWithCharOf(charNow, edgeType)
                                        if (!isFirst) calc('|')
                                        else isFirst = false
                                        if (charNow == charTo) break
                                        charNow++
                                    }
                                }
                                i += 3
                                continue
                            }
                        } else {
                            pushNewNFAWithCharOf(c, edgeType)
                            if (!isFirst) calc('|')
                            else isFirst = false
                        }
                    }
                    escape = false
                }
            }
            i++
        }
        return i
    }

    /**
     * 解析转义
     * 如果结果是单个字符，那么需要后续处理，否则在本函数中处理完成
     * @return Char:转义后的字符  Boolean: 结果是否是在本函数中处理完毕
     * Int: 转义字符长度例如：\n的长度为2；\u000c的长度为5
     */
    fun parseEscape(c: Char, edgeType: EdgeType = EdgeType.NORMAL): Triple<Char, Boolean, Int> {
        return when (c) {
            'n' -> Triple('\n', false, 1)
            'r' -> Triple('\r', false, 1)
            't' -> Triple('\t', false, 1)
            'f' -> Triple('\u000c', false, 1)
            'v' -> Triple('\u000b', false, 1)
            's' -> {
                val (spaceNfa, stateNow) = getSpaceNFA(state, edgeType)
                state = stateNow
                pushNewNFA(spaceNfa)
                Triple('\u0000', true, 1)
            }

            else -> Triple(c, false, 1)
        }
    }

    init {
        //<editor-fold desc="初始化与预处理">
        val initNode = newNode
        startNode.addNext(null, initNode)
        initNode.addNext(null, endNode)
        startNFA = NFA(startNode)
        val initNFA = NFA(initNode)
        nfaStack.add(initNFA)
        //</editor-fold>
        var i = 0
        var escape = false
        while (true) {
            if (i >= regex.length) break
            var c = regex[i]
            if (escape || !allRegOp.contains(c)) {
                if (escape) {
                    val (escChar, handled, indexInc) = parseEscape(c)
                    i += indexInc - 1
                    if (handled) {
                        i++
                        escape = false
                        continue
                    }
                    c = escChar
                }
                tryAddLinker(i, regex)
                pushNewNFAWithCharOf(c)
                escape = false
            } else {
                when {
                    c == '\\' -> {
                        escape = true
                        i++
                        continue
                    }

                    c == '.' -> {
                        tryAddLinker(i, regex)
                        pushNewNFAWithCharOf(c, EdgeType.DOT_ANY)
                    }

                    c == '[' -> {
                        i = handleMiddleContext(i, regex)
                        continue
                    }

                    c == ']' -> throw IllegalRegexException.unexpectedChar(']', i, regex)
                    c == '(' -> {
                        symbolStack.add(c)
                    }

                    c == ')' -> {
                        if (symbolStack.isEmpty()) {
                            throw IllegalRegexException.unexpectedChar(')', i, regex)
                        }
                        var now = symbolStack.removeLast()
                        while (now != '(') {
                            calc(now)
                            if (symbolStack.isEmpty()) {
                                throw IllegalRegexException.unexpectedChar(')', i, regex)
                            }
                            now = symbolStack.removeLast()
                        }
                        tryAddLinker(i, regex)
                    }

                    unaryRegOp.contains(c) -> {
                        calc(c)
                        tryAddLinker(i, regex)
                    }

                    else -> {
                        if (symbolStack.isEmpty()) {
                            symbolStack.add(c)
                        } else {
                            var last = symbolStack.last()
                            while (regOpPriority[c]!! < regOpPriority[last]!!) {
                                last = symbolStack.last()
                                if (regOpPriority[c]!! >= regOpPriority[last]!!) {
                                    break
                                }
                                symbolStack.removeLast()
                                calc(last)
                                if (symbolStack.isEmpty()) {
                                    break
                                }
                            }
                            symbolStack.add(c)
                        }
                    }
                }
            }
            i++
        }
        while (symbolStack.isNotEmpty()) {
            calc(symbolStack.removeLast())
        }
    }

    /**
     * 匹配\s的NFA
     */
    private fun getSpaceNFA(stateStart: Int, edgeType: EdgeType): Pair<NFA<Int, Char>, Int> {
        var stateNow = stateStart
        val nodeIn = NFANode<Int, Char>(stateNow++)
        val nodeOut = NFANode<Int, Char>(stateNow++)
        val result = NFA(nodeIn, nodeOut)
        allNodes.add(nodeIn)
        allNodes.add(nodeOut)
        val chars = arrayOf(' ', '\n', '\r', '\t', '\u000c'/*\f换页符*/, '\u000b'/*\v垂直制表*/)
        for (c in chars) {
            val newNode = NFANode<Int, Char>(stateNow)
            nodeIn.addNext(FAEdge(c, edgeType), newNode)
            newNode.addNext(null, nodeOut)
            allNodes.add(newNode)
            stateNow++
        }
        return Pair(result, stateNow)
    }

    private fun pushNewNFA(nfa: NFA<Int, Char>) {
        val lastNfa = lastNFA
        lastNfa.relinkToNodeOut(nfa.nodeIn)
        nfa.nodeOut.resetNext(null, endNode)
        nfaStack.add(nfa)
    }

    private fun pushNewNFAWithCharOf(c: Char, edgeType: EdgeType = EdgeType.NORMAL) {
        val nowNode = newNode
        val nowNFA = NFA(nowNode)
        val lastNfa = lastNFA
        nowNode.next.clear()
        nowNode.next.putAll(lastNfa.nodeOut.next)
        lastNfa.relinkEdgeToNodeOut(FAEdge(c, edgeType), nowNode)
        nfaStack.add(nowNFA)
    }

    private fun tryAddLinker(i: Int, regex: String) {
        if (i == regex.length - 1
            || regex[i + 1] == '('
            || !allRegOp.contains(regex[i + 1])
        ) {
            if (i != regex.length - 1)
                symbolStack.add(linker)
        }
    }

    private fun calc(c: Char) {
        val right: NFA<Int, Char>
        val left: NFA<Int, Char>
        val last: NFA<Int, Char>
        if (unaryRegOp.contains(c)) {
            right = nfaStack.removeLast()
            left = lastNFA
            last = left
        } else {
            right = nfaStack.removeLast()
            left = nfaStack.removeLast()
            last = lastNFA
        }
        when (c) {
            '|' -> {
                val newNodeIn = newNode
                newNodeIn.addCopyNext(left.nodeOut)
                newNodeIn.addCopyNext(lastNFA.nodeOut)
                last.relinkNullToNodeOut(newNodeIn)
                val newNodeOut = newNode
                newNodeOut.addCopyNext(right.nodeOut)
                right.relinkNullToNodeOut(newNodeOut)
                left.relinkNullToNodeOut(newNodeOut)
                val newNFA = NFA(
                    newNodeIn, newNodeOut
                )
                nfaStack.add(newNFA)
            }

            linker -> {
                left.relinkToNodeOut(right.nodeIn)
                val newNode = NFA(
                    left.nodeIn, right.nodeOut
                )
                nfaStack.add(newNode)
            }

            '*', '+', '?' -> {
                val newNodeIn = newNode
                val newNodeOut = newNode
                val wrapperIn = newNode
                val wrapperOut = newNode
                newNodeIn.addNext(null, wrapperIn)
                wrapperIn.addCopyNext(last.nodeOut)
                wrapperOut.addNext(null, newNodeOut)

                if (c != '?') {
                    wrapperOut.addNext(null, wrapperIn)
                }
                last.relinkNullToNodeOut(newNodeIn)
                newNodeOut.addCopyNext(right.nodeOut)
                right.relinkToNodeOut(wrapperOut)
                if (c != '+') {
                    newNodeIn.addNext(null, newNodeOut)
                }

                nfaStack.add(NFA(newNodeIn, newNodeOut))
            }

            '(' -> throw IllegalRegexException.lackOfChar(')')
        }
    }

    private val lastNFA
        get() = if (nfaStack.isEmpty()) {
            startNFA
        } else nfaStack.last()

    fun getNFA(): NFA<Int, Char> {
        return NFA(startNode, endNode, allNodes)
    }
}

/**
 * Parse regex
 *
 * @param s regex input
 * @return NFA of regex
 */
fun parseRegex(s: String): NFA<Int, Char> {
    return RegexParser(s).getNFA()
}